package algorithm.poj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * id: 1009
 * @author wong.tong@gmail.com
 *
 */
public class EdgeDetection {

	public static void main(String[] args) throws Exception {
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        String line;
        List<String> lines = new ArrayList<String>();
        String[] tmp;
        String s = "";

        line = stdin.readLine();
        int width;
        int[] ps;
        int[] ls;

        while (!"0".equals(line)) {
        	width = Integer.valueOf(line);
        	line = stdin.readLine();
        	while (!"0 0".equals(line)) {
        		lines.add(line);
        		line = stdin.readLine();
        	}
        	ps = new int[lines.size()];
        	ls = new int[lines.size()];
        	for (int i = 0; i < lines.size(); i ++) {
        		line = lines.get(i);
        		tmp = line.split("\\s+");
        		ps[i] = Integer.valueOf(tmp[0]);
        		ls[i] = Integer.valueOf(tmp[1]);
        	}
        	s += edge(width, ps, ls);
        	lines.clear();
        	line = stdin.readLine();
        }

        System.out.println(s);
	}
	
	private static String edge(int w, int[] ps, int[] ls) {

		int total = 0;
		for (int i = 0; i < ls.length; i ++) {
			total += ls[i];
		}
		int h = total/w;
		
		String str = "";
		for (int i = 0; i < total; i ++) {
			str += getEdge(i, w, h, ps, ls) + " ";
		}
		
		return str;
	}

	private static int getEdge(int index, int w, int h, int[] ps, int[] ls) {
		
		int x = index%w, y = index/w;
		int _p = getPixel(x, y, w, h, ps, ls);
		int[] _ps = {
				getPixel(x-1, y-1, w, h, ps, ls), getPixel(x, y-1, w, h, ps, ls), getPixel(x+1, y-1, w, h, ps, ls),
				getPixel(x-1, y, w, h, ps, ls), getPixel(x+1, y, w, h, ps, ls),
				getPixel(x-1, y+1, w, h, ps, ls), getPixel(x, y+1, w, h, ps, ls), getPixel(x+1, y+1, w, h, ps, ls),
		};
		int edge = 0;
		for (int i = 0; i < _ps.length; i ++) {
			if (_ps[i] > 0 && edge < Math.abs(_p-_ps[i])) {
				edge = Math.abs(_p-_ps[i]);
			}
		}
		return edge;
	}
	
	private static int getPixel(int x, int y, int w, int h, int[] ps, int[] ls) {

		
		if (x < 0 || y < 0 || x > w || y > h) { 
			return -1;
		} else {
			int index = w*y + x;
			int idx = 0;
			int sum = 0;
			while (sum <= index && idx < ls.length) {
				sum += ls[idx];
				idx ++;
			}
			
			if (idx <= ps.length) {
				return ps[idx-1];					
			} else {
				return -1;
			}
		}
	}
}
